package dynamicProgramming.SingleSequenceProblem;

/**
 * @author zxc
 * @date 2023/01/19 21:49
 **/

/**
 * 题目 ：翻转字符
 * 题目详述 ：
 * 如果一个由'0' 和 '1'组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是单调递增的。
 * 我们给出一个由字符 '0' 和 '1'组成的字符串 s，我们可以将任何'0' 翻转为'1'或者将'1'翻转为'0'。
 * 返回使 s单调递增的最小翻转次数。
 *
 * 提示：
 * 1 <= s.length <= 20000
 * s 中只包含字符 '0' 和 '1'
 */
public class MinFlipsMonoIncr {
    /**
     * 思路 ：由于翻转字符串需要n个步骤，同时面对字符串中的每个字符时，都会面临选项（是否翻转），同时由于求解最小翻转次数（最优解），直接使用动态规划即可;
     * ===》 使用迭代方法，来实现动态规划;
     *
     * 核心思想 ：确定状态转移方程（动态规划核心）
     * 步骤 ：
     * （1）首先，假设f(i)代表了长度为i的字符串满足题目条件 && 同时第i个字符（最后一个字符）应该为'0';
     *      假设g(i)代表了长度为i的字符串满足题目条件 && 同时第i个字符（最后一个字符）应该为'1';
     *
     * （2）其次，当字符串的最后一个字符实际上是'0'时，（即，当前字符串的最后一个字符确实为'0'）
     *   状态转移方程 ：
     *   a.f(i) = f(i - 1);
     *   ===》 即，代表了当前字符串的最后一个字符实际为'0',而f(i)中最后一个字符应该为字符'0',
     *   同时，若是要去满足题目条件的话，则字符‘0’之前只能够是字符'0';
     *   f(i)所代表的满足条件字符串的最后一个字符应该为'0' && 同时当前字符串的最后一个字符实际上为'0',即不需要翻转当前字符串的最后一个字符
     *   b.g(i) = min(f(i - 1) , g(i - 1)) + 1;
     *   ===》 即，代表了当前字符串的最后一个字符实际为‘0’，而g(i)中最后一个字符应该为字符‘1‘,
     *   同时，若是要去满足题目条件的话，则字符’1’之前可以是字符‘0’或者字符‘1’;
     *   g（i）所带的满足条件字符串的最后一个字符应该为'1' && 同时当前字符串的最后一个字符实际上为'0',即需要去翻转当前字符串的最后一个字符
     *
     * （3）最后，当字符串的最后一个字符实际上是'1'时，
     *  状态转移方程 ：
     *  a.f(i) = f(i - 1) + 1;
     *  ===》 即，代表了当前字符串的最后一个字符实际为'1',而f(i)中最后一个字符应该为字符'0',
     *  同时，若是要去满足题目条件的话，则字符‘0’之前只能够是字符'0';
     *  f(i)所代表的满足条件字符串的最后一个字符应该为'0' && 同时当前字符串的最后一个字符实际上为'1',即需要去翻转当前字符串的最后一个字符
     *  b.g(i) = min(f(i - 1) , g(i - 1));
     *  ===》 即，代表了当前字符串的最后一个字符实际为‘1’，而g(i)中最后一个字符应该为字符‘1‘,
     *  同时，若是要去满足题目条件的话，则字符’1’之前可以是字符‘0’或者字符‘1’;
     *  g（i）所带的满足条件字符串的最后一个字符应该为'1' && 同时当前字符串的最后一个字符实际上为'1',即不需要翻转当前字符串的最后一个字符
     * @param s
     * @return
     */
    public int minFlipsMonoIncr(String s) {
        // 获取所需要进行翻转字符串的长度length
        int length = s.length();
        // 创建两行两列数组
        // 行 ：用来存储 ：
        // temp[0][0] : 1.f(i),即长度为i的字符串满足题目条件 && 同时第i个字符（最后一个字符）应该为'0';
        // temp[0][1] : 2.g(i),即长度为i的字符串满足题目条件 && 同时第i个字符（最后一个字符）应该为'1';
        // 列 ：用来存储
        // temp[i % 2][0] : 1.长度为i字符串的最少翻转次数;
        // temp[(i + 1) % 2][1] : 2.长度为（i + 1）字符串的最少翻转次数;
        /**
         * 为什么只需要设置大小为2的数组？
         * 原因 ：
         * （1）由于f(i)有且仅由f(i-1)决定 && 同时g(i)也是有且仅由f(i-1)和g(i-1)所决定;
         * （2）同时，使用迭代法的话，是从小问题进行入手，先将小问题结果求解出来，再将小问题结果合并起来，来解决大问题;
         * （3）即，先求解出f(0)和g(0),后再根据f(0)和g(0)来求解出f(1)和g(1)...依次迭代,直至根据f(n-1)和g(n-1)来求解出f(n)和g(n);
         * ===》 结论 ：即，为求解出f(i+1)/g(i+1),只需要使用数组来存储f(i)/g(i)结果即可;
         */
        int[][] temp = new int[2][2];
        // 由于状态转移方程的隐性条件为 i >= 1，所以长度为1字符串中的唯一字符决定了f(0)和g(0);
        // （1）若是唯一字符为‘0’的话，即f(0) == 0（无需翻转） && g(0) == 1（需要翻转）;
        // （2）若是唯一字符为‘1’的话，即f(0) == 1（需要翻转） && g(0) == 0（无需翻转）;
        if(s.charAt(0) == '0'){
            temp[0][0] = 0;
            temp[1][0] = 1;
        }
        else {
            temp[0][0] = 1;
            temp[1][0] = 0;
        }
        // 迭代实现动态规划核心代码 ：
        // 注意的是，需要满足状态转移方程的隐性条件，即i >= 1;
        for(int i = 1 ; i < length ; i++){
            // 获取当前遍历字符串的最后一个字符;
            /**
             * 由于已经存储了长度为i字符串的最少修改次数 f(i)/g(i),
             * ===》 长度为i+1字符串的最少修改次数，是根据第i+1个字符来决定的;
             */
            char ch = s.charAt(i);
//         （1）若是字符串的最后一个字符为‘0’时，
//          ===》 状态转移方程 ：
//          a.f(i) = f(i - 1);
//          b.g(i) = min(f(i - 1) , g(i - 1)) + 1;、
//         （2）若是字符串的最后一个字符为‘1’时，
//          ===》状态转移方程 ：
//          a.f(i) = f(i - 1) + 1;
//          b.g(i) = min(f(i - 1) , g(i - 1));
            if(ch == '0'){
                temp[0][i % 2] = temp[0][(i - 1) % 2];
                temp[1][i % 2] = Math.min(temp[0][(i - 1) % 2] , temp[1][(i - 1) % 2]) + 1;
            }
            else {
                temp[0][i % 2] = temp[0][(i - 1) % 2] + 1;
                temp[1][i % 2] = Math.min(temp[0][(i - 1) % 2] , temp[1][(i - 1) % 2]);
            }
        }
        // 由于经过上述的迭代代码后，
        // 最终的f(i)结果，已经被存储在数组元素temp[0][(length - 1) % 2]中;
        // 最终的g(i)结果，已经被存储在数组元素temp[1][(length - 1) % 2]中;
        return Math.min(temp[0][(length - 1) % 2] , temp[1][(length - 1) % 2]);
    }
}
